1795D - Triangle Coloring - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
const ll inf = 1e9 + 7;
#define speedup ios_base::sync_with_stdio(false);cin.tie(NULL);
ll gcd(ll a, ll b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}
namespace modop {
	ll madd(ll a, ll b) {
		return (a + b) % mod;
	}
	ll msub(ll a, ll b) {
		return (((a - b) % mod) + mod) % mod;
	}
	ll mmul(ll a, ll b) {
		return ((a % mod) * (b % mod)) % mod;
	}
	ll mpow(ll base, ll exp) {
		ll res = 1;
		while (exp) {
			if (exp % 2 == 1) {
				res = (res * base) % mod;
			}
			exp >>= 1;
			base = (base * base) % mod;
		}
		return res;
	}
	ll minv(ll base) {
		return mpow(base, mod - 2);
	}
	ll mdiv(ll a, ll b) {
		return mmul(a, minv(b));
	}
	const ll FACTORIAL_SIZE = 1.1e6;
	ll fact[FACTORIAL_SIZE], ifact[FACTORIAL_SIZE];
	void gen_factorial(ll n) {
		fact[0] = fact[1] = ifact[0] = ifact[1] = 1;

		for (ll i = 2; i <= n; i++) {
			fact[i] = (i * fact[i - 1]) % mod;
		}
		ifact[n] = minv(fact[n]);
		for (ll i = n - 1; i >= 2; i--) {
			ifact[i] = ((i + 1) * ifact[i + 1]) % mod;
		}
	}
	ll nck(ll n, ll k) {
		if (k == 0) {
			return 1;
		}
		ll den = (ifact[k] * ifact[n - k]) % mod;
		return (den * fact[n]) % mod;
	}
}
using namespace modop;
int main() {
	gen_factorial(300005);
	ll n;
	cin >> n;
	vector<int> v(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	ll ans = 1;
	ll cc = 0;
	for (int i = 1; i <= n; i += 3) {
		cc++;
		int val1 = v[i];
		int val2 = v[i + 1];
		int val3 = v[i + 2];
		map<int, int> ct;
		ct[val1]++;
		ct[val2]++;
		ct[val3]++;
		if (ct.size() == 1) {
			ans *= (3ll);
			ans %= mod;
		}
		if (ct.size() == 2) {
			auto it1 = *ct.begin();
			auto it2 = *ct.rbegin();
			int f = it1.second;
			int s = it2.second;
			if (s > f) {
				ans *= (1ll);
				ans %= mod;
			}
			else {
				ans *= (2ll);
				ans %= mod;
			}
		}
	}
	ll tomul = nck(cc, cc / 2);
	ans = mmul(ans, tomul);
	cout << ans << endl;
}